{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Score Words Formed by Letters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #string #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #字符串 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScoreWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得分最高的单词集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你将会得到一份单词表&nbsp;<code>words</code>，一个字母表&nbsp;<code>letters</code>&nbsp;（可能会有重复字母），以及每个字母对应的得分情况表&nbsp;<code>score</code>。</p>\n",
    "\n",
    "<p>请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由&nbsp;<code>letters</code>&nbsp;里的字母拼写出的&nbsp;<strong>任意</strong>&nbsp;属于 <code>words</code>&nbsp;单词子集中，分数最高的单词集合的得分。</p>\n",
    "\n",
    "<p>单词拼写游戏的规则概述如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>玩家需要用字母表&nbsp;<code>letters</code> 里的字母来拼写单词表&nbsp;<code>words</code>&nbsp;中的单词。</li>\n",
    "\t<li>可以只使用字母表&nbsp;<code>letters</code> 中的部分字母，但是每个字母最多被使用一次。</li>\n",
    "\t<li>单词表 <code>words</code>&nbsp;中每个单词只能计分（使用）一次。</li>\n",
    "\t<li>根据字母得分情况表<code>score</code>，字母 <code>&#39;a&#39;</code>,&nbsp;<code>&#39;b&#39;</code>,&nbsp;<code>&#39;c&#39;</code>, ... ,&nbsp;<code>&#39;z&#39;</code> 对应的得分分别为 <code>score[0]</code>, <code>score[1]</code>,&nbsp;...,&nbsp;<code>score[25]</code>。</li>\n",
    "\t<li>本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [&quot;dog&quot;,&quot;cat&quot;,&quot;dad&quot;,&quot;good&quot;], letters = [&quot;a&quot;,&quot;a&quot;,&quot;c&quot;,&quot;d&quot;,&quot;d&quot;,&quot;d&quot;,&quot;g&quot;,&quot;o&quot;,&quot;o&quot;], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]\n",
    "<strong>输出：</strong>23\n",
    "<strong>解释：</strong>\n",
    "字母得分为  a=1, c=9, d=5, g=3, o=2\n",
    "使用给定的字母表 letters，我们可以拼写单词 &quot;dad&quot; (5+1+5)和 &quot;good&quot; (3+2+2+5)，得分为 23 。\n",
    "而单词 &quot;dad&quot; 和 &quot;dog&quot; 只能得到 21 分。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [&quot;xxxz&quot;,&quot;ax&quot;,&quot;bx&quot;,&quot;cx&quot;], letters = [&quot;z&quot;,&quot;a&quot;,&quot;b&quot;,&quot;c&quot;,&quot;x&quot;,&quot;x&quot;,&quot;x&quot;], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]\n",
    "<strong>输出：</strong>27\n",
    "<strong>解释：</strong>\n",
    "字母得分为  a=4, b=4, c=4, x=5, z=10\n",
    "使用给定的字母表 letters，我们可以组成单词 &quot;ax&quot; (4+5)， &quot;bx&quot; (4+5) 和 &quot;cx&quot; (4+5) ，总得分为 27 。\n",
    "单词 &quot;xxxz&quot; 的得分仅为 25 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [&quot;leetcode&quot;], letters = [&quot;l&quot;,&quot;e&quot;,&quot;t&quot;,&quot;c&quot;,&quot;o&quot;,&quot;d&quot;], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "字母 &quot;e&quot; 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 14</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 15</code></li>\n",
    "\t<li><code>1 &lt;= letters.length &lt;= 100</code></li>\n",
    "\t<li><code>letters[i].length == 1</code></li>\n",
    "\t<li><code>score.length ==&nbsp;26</code></li>\n",
    "\t<li><code>0 &lt;= score[i] &lt;= 10</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;和&nbsp;<code>letters[i]</code>&nbsp;只包含小写的英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-score-words-formed-by-letters](https://leetcode.cn/problems/maximum-score-words-formed-by-letters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-score-words-formed-by-letters](https://leetcode.cn/problems/maximum-score-words-formed-by-letters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"dog\",\"cat\",\"dad\",\"good\"]\\n[\"a\",\"a\",\"c\",\"d\",\"d\",\"d\",\"g\",\"o\",\"o\"]\\n[1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]', '[\"xxxz\",\"ax\",\"bx\",\"cx\"]\\n[\"z\",\"a\",\"b\",\"c\",\"x\",\"x\",\"x\"]\\n[4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]', '[\"leetcode\"]\\n[\"l\",\"e\",\"t\",\"c\",\"o\",\"d\"]\\n[0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        m = len(words)\n",
    "        ans = 0\n",
    "        C=Counter(letters)\n",
    "        for i in range(1,1<<m):\n",
    "            wordCount=defaultdict(int)\n",
    "            for j in range(m):\n",
    "                if (i & (1<<j)) ==0:\n",
    "                    continue\n",
    "                for k in words[j]:\n",
    "                    wordCount[k] +=1\n",
    "            ok = True\n",
    "            sum = 0\n",
    "            for  j in range(26):\n",
    "                sum += score[j] * wordCount[chr(ord('a')+j)]\n",
    "                ok = ok and (wordCount[chr(ord('a')+j)] <= C[chr(ord('a')+j)])\n",
    "            if ok :\n",
    "                ans = max(ans,sum)\n",
    "        return ans \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        #copy zero\n",
    "        def dfs(i,n,cur):\n",
    "            if i ==n:\n",
    "                return 0\n",
    "            \n",
    "            ret = dfs(i+1,n,cur)\n",
    "            ithletter = collections.Counter(words[i])\n",
    "            check = all(cur[k]>= v for k,v in ithletter.items())\n",
    "            if check:\n",
    "                ithscore = sum(score[ord(k)-97]*v for k, v in ithletter.items() )\n",
    "                cur -= ithletter\n",
    "                ret = max(ret,ithscore+ dfs(i+1,n,cur))\n",
    "                cur += ithletter\n",
    "            return ret\n",
    "        \n",
    "        n = len(words)\n",
    "        cletter = collections.Counter(letters)\n",
    "        return dfs(0,n,cletter)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "        self.ans = 0\n",
    "        left = Counter(letters)\n",
    "        def dfs(total, curPos, left):\n",
    "            if curPos == len(words):\n",
    "                self.ans = max(self.ans, total)\n",
    "                return\n",
    "            dfs(total, curPos+1, left)\n",
    "            if Counter(words[curPos]) <= left:\n",
    "                addtion = sum([score[n] for n in words[curPos]])\n",
    "                dfs(total + addtion, curPos+1, left - Counter(words[curPos]))\n",
    "        dfs(0, 0, left)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "       def dfs(i: int, j: int) -> None:\n",
    "          if i == n:\n",
    "             nonlocal res\n",
    "             res = max(res, j)\n",
    "             return\n",
    "          # 不选 \n",
    "          dfs(i + 1, j)\n",
    "          # 选\n",
    "          cur = [0] * 26\n",
    "          for c in words[i]:\n",
    "             cur[ord(c) - ord('a')] += 1\n",
    "          if all(a >= b for a, b in zip(cnts, cur)):\n",
    "             s = 0\n",
    "             for k in range(26):\n",
    "                s += cur[k] * score[k]\n",
    "                cnts[k] -= cur[k]\n",
    "             dfs(i + 1, j + s)\n",
    "             for k in range(26):\n",
    "                cnts[k] += cur[k]\n",
    "       n = len(words)\n",
    "       cnts = [0] * 26\n",
    "       for c in letters:\n",
    "          cnts[ord(c) - ord('a')] += 1\n",
    "       res = 0\n",
    "       dfs(0, 0)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        # 每个单词的得分情况\n",
    "        ws = []\n",
    "        us = [Counter(word) for word in words]\n",
    "        total = Counter(letters)\n",
    "\n",
    "        for word in words:\n",
    "            cur = 0\n",
    "            for ch in word:\n",
    "                cur += score[ord(ch) - ord('a')]\n",
    "            ws.append(cur)\n",
    "        \n",
    "        def satisfied(cnt1, cnt2):\n",
    "            chs = [chr(i + 97) for i in range(26)]\n",
    "            for ch in chs:\n",
    "                if cnt1[ch] > cnt2[ch]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 枚举每个单词选不选\n",
    "        ans = 0\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = Counter()\n",
    "            curs = 0\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += us[i]\n",
    "                    curs += ws[i]\n",
    "            if satisfied(cnt, total):\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        cnt = [0] * 26\n",
    "        for c in letters: cnt[ord(c[0]) - ord('a')] += 1\n",
    "        res = 0\n",
    "        for s in range(1 << n):\n",
    "            cur = [0] * 26\n",
    "            for i in range(n):\n",
    "                if s & (1 << i) == 0: continue\n",
    "                for c in words[i]: cur[ord(c) - ord('a')] += 1\n",
    "            \n",
    "            flag = True\n",
    "            sc = 0\n",
    "            for i in range(26):\n",
    "                sc += cur[i] * score[i]\n",
    "                if cur[i] > cnt[i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag: res = max(res, sc)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        self.words = words\n",
    "        self.words_cnt_list = [collections.Counter(word) for word in words]\n",
    "        self.letter_cnt_map = collections.Counter(letters)\n",
    "        self.score = score\n",
    "        self.score_max = 0\n",
    "        self.dfs(0, 0)\n",
    "        return self.score_max\n",
    "\n",
    "    def dfs(self, cur_score, idx):\n",
    "        if idx >= len(self.words):\n",
    "            self.score_max = max(self.score_max, cur_score)\n",
    "            return\n",
    "\n",
    "        can_spill = True\n",
    "        for k in self.words_cnt_list[idx]:\n",
    "            if self.words_cnt_list[idx][k] > self.letter_cnt_map[k]:\n",
    "                can_spill = False\n",
    "                break\n",
    "\n",
    "        self.dfs(cur_score, idx + 1)\n",
    "\n",
    "        if can_spill:\n",
    "            for k in self.words_cnt_list[idx]:\n",
    "                self.letter_cnt_map[k] -= self.words_cnt_list[idx][k]\n",
    "                cur_score += self.score[ord(k)-ord('a')] * self.words_cnt_list[idx][k]\n",
    "            self.dfs(cur_score, idx + 1)\n",
    "            for k in self.words_cnt_list[idx]:\n",
    "                self.letter_cnt_map[k] += self.words_cnt_list[idx][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        a, n = 0, len(words)\n",
    "        lc = Counter(letters)\n",
    "\n",
    "        for i in range(1 << n):\n",
    "            wc = Counter(\"\".join([words[j] for j in range(n) if 1 << j & i]))\n",
    "            if all(wc[c] <= lc[c] for c in wc):\n",
    "                a = max(a, sum(v * score[ord(c)-ord('a')] for c, v in wc.items()))\n",
    "                \n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        total = Counter(letters)\n",
    "        ws = []\n",
    "        for word in words:\n",
    "            tmp = 0\n",
    "            for ch in word:\n",
    "                tmp += score[ord(ch) - ord('a')]\n",
    "            ws.append(tmp)\n",
    "\n",
    "        def check(cnt, total):\n",
    "            for k in cnt.keys():\n",
    "                if cnt[k] > total[k]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        n = len(words)\n",
    "        ans = 0\n",
    "        for mask in range(1, 2 ** n):\n",
    "            curs = 0\n",
    "            flag = True\n",
    "            cnt = Counter()\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    curs += ws[i]\n",
    "                    cnt += Counter(words[i])\n",
    "                    if not check(cnt, total):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        cnt = Counter(letters)\n",
    "        n = len(words)\n",
    "        def dfs(i,cnt):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            #不选\n",
    "            ans = dfs(i+1,cnt)\n",
    "            #选\n",
    "            cv = Counter(words[i])\n",
    "            if all(v<=cnt[k] for k,v in cv.items()):\n",
    "               ans = max(ans,sum(score[ord(k)-ord('a')]*v  for k,v in cv.items()) + dfs(i+1,cnt-cv))\n",
    "            return ans        \n",
    "        return dfs(0,cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        alph = [0]*26\n",
    "        for l in letters:\n",
    "            alph[ord(l)-97] += 1\n",
    "        @cache\n",
    "        def count(index):\n",
    "            maxi = 0\n",
    "            for i in range(len(words)):\n",
    "                if (index >> i) % 2 == 0:\n",
    "                    can = True\n",
    "                    value = 0\n",
    "                    for w in words[i]:\n",
    "                        alph[ord(w)-97] -= 1\n",
    "                        value += score[ord(w)-97]\n",
    "                        if alph[ord(w)-97] < 0: can = False\n",
    "                    if can: maxi = max(maxi, count(index|1<<i)+value)\n",
    "                    for w in words[i]:\n",
    "                        alph[ord(w)-97] += 1\n",
    "            return maxi\n",
    "\n",
    "        return count(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        score = dict(zip(ascii_lowercase, score))  # 字母对应的分数\n",
    "\n",
    "        def dfs(i: int, total: int) -> None:\n",
    "            if i < 0:  # base case\n",
    "                nonlocal ans\n",
    "                ans = max(ans, total)\n",
    "                return\n",
    "\n",
    "            # 不选 words[i]\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            # 选 words[i]\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if left[c] == 0:  # 剩余字母不足\n",
    "                    for c in words[i][:j]:  # 撤销\n",
    "                        left[c] += 1\n",
    "                    return\n",
    "                left[c] -= 1  # 减少剩余字母\n",
    "                total += score[c]  # 累加得分\n",
    "\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            # 恢复现场\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "\n",
    "        dfs(len(words) - 1, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        cnt = [0] * 26\n",
    "        for _, x in enumerate(letters):\n",
    "            cnt[ord(x) - 97] += 1\n",
    "        ans = 0\n",
    "        def dfs(i: int, v: int) -> None:\n",
    "            nonlocal ans\n",
    "            if i >= len(words):\n",
    "                ans = max(ans, v)\n",
    "                return\n",
    "            # 不选第i个word\n",
    "            dfs(i + 1, v)\n",
    "            # 选第i个word\n",
    "            ok = True\n",
    "            for _, c in enumerate(words[i]):\n",
    "                if cnt[ord(c) - 97] == 0:\n",
    "                    ok = False\n",
    "                v += score[ord(c) - 97]\n",
    "                cnt[ord(c) - 97] -= 1\n",
    "            if ok:                  # 如果为False表示剩余单词数不足，无法选第i个word\n",
    "                dfs(i + 1, v)\n",
    "            # 恢复现场\n",
    "            for _, c in enumerate(words[i]):\n",
    "                cnt[ord(c) - 97] += 1\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        # 每个单词的得分情况\n",
    "        ws = []\n",
    "        us = [Counter(word) for word in words]\n",
    "        total = Counter(letters)\n",
    "\n",
    "        for word in words:\n",
    "            cur = 0\n",
    "            for ch in word:\n",
    "                cur += score[ord(ch) - ord('a')]\n",
    "            ws.append(cur)\n",
    "        \n",
    "        def satisfied(cnt1, cnt2):\n",
    "            chs = [chr(i + 97) for i in range(26)]\n",
    "            for ch in chs:\n",
    "                if cnt1[ch] > cnt2[ch]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 枚举每个单词选不选\n",
    "        ans = 0\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = Counter()\n",
    "            curs = 0\n",
    "            flag = True\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += us[i]\n",
    "                    curs += ws[i]\n",
    "                    if not satisfied(cnt, total):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ans=0\n",
    "        left=Counter(letters)\n",
    "        score=dict(zip(ascii_lowercase,score))\n",
    "\n",
    "        def dfs(i,total):\n",
    "            if i<0:\n",
    "                nonlocal ans\n",
    "                ans=max(ans,total)\n",
    "                return\n",
    "            dfs(i-1,total)\n",
    "\n",
    "            for j,c in enumerate(words[i]):\n",
    "                if left[c]==0:\n",
    "                    for c in words[i][:j]:\n",
    "                        left[c]+=1\n",
    "                    return\n",
    "                left[c]-=1\n",
    "                total+=score[c]\n",
    "            dfs(i-1,total)\n",
    "\n",
    "            for c in words[i]:\n",
    "                left[c]+=1\n",
    "        \n",
    "        dfs(len(words)-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        \n",
    "        n = len(words)\n",
    "        left = Counter(letters)\n",
    "        ws = []\n",
    "        for word in words:\n",
    "            tmp = 0\n",
    "            for ch in word:\n",
    "                tmp += score[ord(ch) - ord('a')]\n",
    "            ws.append(tmp)\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        def dfs(i, curs):\n",
    "            nonlocal left\n",
    "            \n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, curs)\n",
    "                return\n",
    "            \n",
    "            # 不管i位置的数字\n",
    "            dfs(i-1, curs)\n",
    "\n",
    "\n",
    "            # 可行的话考虑i位置的数字：\n",
    "            flag = True\n",
    "            cnt = Counter(words[i])\n",
    "            for k in cnt:\n",
    "                if cnt[k] > left[k]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                left -= cnt\n",
    "                curs += ws[i]\n",
    "                dfs(i-1, curs)\n",
    "                left += cnt\n",
    "        \n",
    "\n",
    "        dfs(n-1, 0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        ans = 0\n",
    "        cnt = Counter(letters)\n",
    "        d = dict(zip(ascii_lowercase,score))\n",
    "        def dfs(i,val):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans,val)\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i-1,val)\n",
    "            # 选\n",
    "            for j,c in enumerate(words[i]):\n",
    "                if cnt[c] == 0:\n",
    "                    # 恢复前面的\n",
    "                    for c in words[i][:j]:\n",
    "                        cnt[c] += 1\n",
    "                    return \n",
    "                cnt[c] -= 1\n",
    "                val += d[c]\n",
    "            dfs(i-1,val)\n",
    "            # 恢复现场\n",
    "            for c in words[i]:\n",
    "                cnt[c] += 1\n",
    "        dfs(n-1,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        def lt1255(words,letters,scores):\n",
    "            d=defaultdict(int)\n",
    "            for ch in letters:d[ch]+=1\n",
    "            n=len(words)\n",
    "            word_score=defaultdict(int)\n",
    "            for word in words:\n",
    "                word_score[word]=sum([scores[ord(ch)-ord('a')] for ch in word])\n",
    "            def is_available(mask):\n",
    "                temp=[]\n",
    "                idx=n-1\n",
    "                while mask>0:\n",
    "                    if mask&1:temp.append(words[idx])\n",
    "                    mask>>=1\n",
    "                    idx-=1\n",
    "                d_=defaultdict(int)\n",
    "                for word in temp:\n",
    "                    for ch in word:\n",
    "                        d_[ch]+=1\n",
    "                        if d_[ch]>d[ch]:return False\n",
    "                return True\n",
    "            dp=[0]*(1<<n)\n",
    "            for i in range(1,1<<n):\n",
    "                if is_available(i):\n",
    "                    temp=i\n",
    "                    idx=n-1\n",
    "                    while temp:\n",
    "                        if temp&1:dp[i]+=word_score[words[idx]]\n",
    "                        idx-=1\n",
    "                        temp>>=1\n",
    "            return max(dp)\n",
    "        return lt1255(words,letters,score)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        def dfs(i, l):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            s = 0\n",
    "            l2 = l\n",
    "            for c in words[i]:\n",
    "                if c not in l2:\n",
    "                    return dfs(i+1, l)\n",
    "                s += score[ord(c)-ord('a')]\n",
    "                l2 = l2.replace(c, '', 1)\n",
    "\n",
    "            return max(dfs(i+1, l), s + dfs(i+1, l2))\n",
    "        return dfs(0, \"\".join(letters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "        self.ans = 0\n",
    "        left = Counter(letters)\n",
    "        def dfs(total, curPos, left):\n",
    "            if curPos == len(words):\n",
    "                self.ans = max(self.ans, total)\n",
    "                return\n",
    "            dfs(total, curPos+1, left)\n",
    "            if Counter(words[curPos]) <= left:\n",
    "                addtion = sum([score[n] for n in words[curPos]])\n",
    "                dfs(total + addtion, curPos+1, left - Counter(words[curPos]))\n",
    "        dfs(0, 0, left)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        c = Counter(letters)\n",
    "\n",
    "        m = len(words)\n",
    "        ans = 0\n",
    "        for i in range(1, 1<<m + 1):\n",
    "            cnt = Counter()\n",
    "            for j in range(m):\n",
    "                if i & (1<<j):\n",
    "                    cnt += Counter(words[j])\n",
    "            s = 0\n",
    "            flag = True\n",
    "            for key, value in cnt.items():\n",
    "                if value > c[key]:\n",
    "                    flag = False\n",
    "                    break\n",
    "                s += score[ord(key) - ord('a')] * value\n",
    "            \n",
    "            if flag:\n",
    "                if s > ans:\n",
    "                    ans = s\n",
    "        return ans\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        def dfs(i, total):\n",
    "            if i<0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, total)\n",
    "                return\n",
    "            dfs(i-1, total)\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if left[c] == 0:\n",
    "                    for c in words[i][:j]:\n",
    "                        left[c] += 1\n",
    "                    return\n",
    "                left[c] -= 1\n",
    "                total += score[c]\n",
    "            dfs(i-1, total)\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "        dfs(len(words) - 1, 0)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "\n",
    "        # 每个单词的得分情况\n",
    "        ws = []\n",
    "        us = [Counter(word) for word in words]\n",
    "        total = Counter(letters)\n",
    "\n",
    "        for word in words:\n",
    "            cur = 0\n",
    "            for ch in word:\n",
    "                cur += score[ord(ch) - ord('a')]\n",
    "            ws.append(cur)\n",
    "        \n",
    "        def satisfied(cnt1, cnt2):\n",
    "            for ch in cnt1.keys():\n",
    "                if cnt1[ch] > cnt2[ch]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 枚举每个单词选不选\n",
    "        ans = 0\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = Counter()\n",
    "            curs = 0\n",
    "            flag = True\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += us[i]\n",
    "                    curs += ws[i]\n",
    "                    if not satisfied(cnt, total):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        # 题意你需要用letters中的字母去拼写单词，如果拼写的单词\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        score = dict(zip(ascii_lowercase,score))\n",
    "        def dfs(i,total):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans,total)\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i-1,total)\n",
    "            # 选word[i]\n",
    "            for j,c in enumerate(words[i]):\n",
    "                if left[c] == 0:\n",
    "                    for c in words[i][:j]:\n",
    "                        left[c] += 1\n",
    "                    return\n",
    "                left[c] -= 1\n",
    "                total += score[c]\n",
    "            dfs(i-1,total)\n",
    "            # 恢复现场\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "        dfs(len(words)-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        c = Counter(letters)\n",
    "        ans = 0\n",
    "        n = len(words)\n",
    "        for i in range(1<<n + 1):\n",
    "            cnt = Counter()\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    cnt += Counter(words[j])\n",
    "            s = 0\n",
    "            flag = True\n",
    "            for key, value in cnt.items():\n",
    "                if value > c[key]:\n",
    "                    flag = False\n",
    "                    break\n",
    "                s += value * score[ord(key) - ord('a')]\n",
    "            if flag: ans = max(ans, s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "        self.ans = 0\n",
    "        left = Counter(letters)\n",
    "        def dfs(total, curPos, left):\n",
    "            if curPos == len(words):\n",
    "                self.ans = max(self.ans, total)\n",
    "                return\n",
    "            dfs(total, curPos+1, left)\n",
    "            if Counter(words[curPos]) <= left:\n",
    "                addtion = sum([score[n] for n in words[curPos]])\n",
    "                dfs(total + addtion, curPos+1, left - Counter(words[curPos]))\n",
    "        dfs(0, 0, left)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        cnt = Counter(letters)\n",
    "        n = len(words)\n",
    "        def f(i: int, cnt: Counter) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            # 对于 words[i] 有选或不选两种可能\n",
    "            res = f(i + 1, cnt)\n",
    "            need = Counter(words[i])\n",
    "            if all(cnt[c] >= need[c] for c in words[i]):\n",
    "                res = max(res, f(i + 1, cnt - need) + sum(score[ord(c) - ord('a')] for c in words[i]))\n",
    "            return res\n",
    "        return f(0, cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        score = dict(zip(ascii_lowercase, score))  # 字母对应的分数\n",
    "\n",
    "        def dfs(i: int, left: Counter) -> int:\n",
    "            if i < 0:  # base case\n",
    "                return 0\n",
    "\n",
    "            # 不选 words[i]\n",
    "            res = dfs(i - 1, left)\n",
    "\n",
    "            # 选 words[i]\n",
    "            cw = Counter(words[i])\n",
    "            if all(v <= left.get(k, 0) for k, v in cw.items()):  # 可以选\n",
    "                res = max(res, sum(score[c] for c in words[i]) + dfs(i - 1, left - cw))\n",
    "            return res\n",
    "\n",
    "        return dfs(len(words) - 1, Counter(letters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        lc = Counter(letters)\n",
    "        a = 0\n",
    "\n",
    "        def dfs(i, total):\n",
    "            if i >= n:\n",
    "                nonlocal a\n",
    "                a = max(a, total)\n",
    "                return\n",
    "\n",
    "\n",
    "            dfs(i+1, total)\n",
    "\n",
    "\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if lc[c] <= 0:\n",
    "                    for c in words[i][:j]:\n",
    "                        lc[c] += 1\n",
    "                    return\n",
    "                lc[c] -= 1\n",
    "                total += score[ord(c)-ord('a')]\n",
    "            dfs(i+1, total)\n",
    "            for c in words[i]:\n",
    "                lc[c] += 1\n",
    "\n",
    "            return\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        cur = [0] * len(words)\n",
    "        letterCount = []\n",
    "        wordScore = [0] * len(words)\n",
    "        for i in range(len(words)):\n",
    "            letterCount.append([0] * 26)\n",
    "            for c in words[i]:\n",
    "                k = ord(c) - ord('a')\n",
    "                letterCount[i][k] += 1\n",
    "                wordScore[i] += score[k]\n",
    "\n",
    "        package = [0] * 26\n",
    "        for c in letters:\n",
    "            package[ord(c) - ord('a')] += 1\n",
    "\n",
    "        currentScore = 0\n",
    "        res = 0\n",
    "        currentLetters = [0] * 26\n",
    "        while cur[-1] < 2:\n",
    "            cur[0] += 1\n",
    "            if cur[0] == 1:\n",
    "                currentScore += wordScore[0]\n",
    "                self.A(currentLetters, letterCount[0])\n",
    "            else:\n",
    "                i = 0\n",
    "                while cur[i] == 2:\n",
    "                    cur[i] = 0\n",
    "                    currentScore -= wordScore[i]\n",
    "                    self.D(currentLetters, letterCount[i])\n",
    "                    i += 1\n",
    "                    if i == len(cur):\n",
    "                        break \n",
    "                    cur[i] += 1\n",
    "                if i != len(cur):\n",
    "                    currentScore += wordScore[i]\n",
    "                    self.A(currentLetters, letterCount[i])\n",
    "                else:\n",
    "                    break\n",
    "            if self.C(currentLetters, package):\n",
    "                res = max(res, currentScore)\n",
    "        return res\n",
    "    \n",
    "    def C(self, x, y):\n",
    "        for i in range(len(x)):\n",
    "            if x[i] > y[i]:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def A(self, x, y):\n",
    "        for i in range(len(x)):\n",
    "            x[i] += y[i]\n",
    "    \n",
    "    def D(self, x, y):\n",
    "        for i in range(len(x)):\n",
    "            x[i] -= y[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        def lt1255(words,letters,scores):\n",
    "            d=defaultdict(int)\n",
    "            for ch in letters:d[ch]+=1\n",
    "            n=len(words)\n",
    "            word_score=defaultdict(int)\n",
    "            for word in words:\n",
    "                word_score[word]=sum([scores[ord(ch)-ord('a')] for ch in word])\n",
    "            def is_available(mask):\n",
    "                temp=[]\n",
    "                idx=n-1\n",
    "                while mask>0:\n",
    "                    if mask&1:temp.append(words[idx])\n",
    "                    mask>>=1\n",
    "                    idx-=1\n",
    "                d_=defaultdict(int)\n",
    "                for word in temp:\n",
    "                    for ch in word:\n",
    "                        d_[ch]+=1\n",
    "                        if d_[ch]>d[ch]:return False\n",
    "                return True\n",
    "            dp=[0]*(1<<n)\n",
    "            for i in range(1,1<<n):\n",
    "                if dp[i]==-1:continue\n",
    "                if is_available(i):\n",
    "                    temp=i\n",
    "                    idx=n-1\n",
    "                    while temp:\n",
    "                        if temp&1:dp[i]+=word_score[words[idx]]\n",
    "                        idx-=1\n",
    "                        temp>>=1\n",
    "                else:\n",
    "                    dp[i]=-1\n",
    "                    for j in range(i+1,1<<n):\n",
    "                        if i&j==i:dp[j]=-1\n",
    "            return max(max(dp),0)\n",
    "        return lt1255(words,letters,score)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:#tuple或字典dp\n",
    "        letters=Counter(letters)\n",
    "        k=tuple([letters[chr(ord('a')+i)] for i in range(26)])\n",
    "        dp=Counter()\n",
    "        dp[deepcopy(k)]=0\n",
    "        for w in words:\n",
    "            ct=Counter(w)\n",
    "            tp=dp.copy()#deepcopy(dp)\n",
    "            for j in tp:\n",
    "                l=list(j)\n",
    "                canJoin=True\n",
    "                for i in ct:\n",
    "                    if ct[i]>l[ord(i)-ord('a')]:\n",
    "                        canJoin=False\n",
    "                        break\n",
    "                    l[ord(i)-ord('a')]-=ct[i]\n",
    "                if not canJoin:continue\n",
    "                l=tuple(l)\n",
    "                sm=sum(score[ord(i)-ord('a')]*ct[i] for i in ct)\n",
    "                if l not in dp:dp[l]=dp[j]+sm\n",
    "                else:dp[l]=max(dp[j]+sm,dp[l])\n",
    "            # dp[letters]=0\n",
    "        # print(k)\n",
    "        # print(dp.most_common(1)[0])\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        \n",
    "        # 如果比letters中的要多，则得分为0\n",
    "        # 如果比letters中的要少，则统计份数，和max值进行比较\n",
    "        # 难点在于找出所有单词的组合\n",
    "\n",
    "        # 统计letters的字母数\n",
    "        dl = {}\n",
    "        r = 0\n",
    "        for l in letters:\n",
    "            if l not in dl:\n",
    "                dl[l] = 1\n",
    "            else:\n",
    "                dl[l] += 1\n",
    "\n",
    "        for i in range(1, len(words)+1):\n",
    "            # 找出所有单词的组合\n",
    "            combinations = itertools.combinations(words, i)\n",
    "            # 将每个单词组合的字母数group统计\n",
    "            for c in combinations:\n",
    "                d = {}\n",
    "                for w in c:\n",
    "                    for ww in w:\n",
    "                        if ww not in d:\n",
    "                            d[ww] = 1\n",
    "                        else:\n",
    "                            d[ww] += 1\n",
    "                # print(c, d)\n",
    "                hege = 1\n",
    "                for k in d:\n",
    "                    if k in dl and d[k] <= dl[k]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        hege = 0\n",
    "                        break\n",
    "                if hege:\n",
    "                    # 计算得分\n",
    "                    s = 0\n",
    "                    for k in d:\n",
    "                        s += (score[ord(k)-ord('a')] *d[k])\n",
    "                    if s > r:\n",
    "                        r = s\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        \n",
    "        def f(i: int, cnt: Counter) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            # 当前单词选或不选\n",
    "            res = f(i - 1, cnt) # 不选当前单词\n",
    "            ct = Counter(words[i])\n",
    "            if all(v <= cnt.get(k, 0) for k, v in ct.items()):\n",
    "                res = max(res, sum(score[ord(c) - ord('a')] for c in words[i]) + f(i - 1, cnt - ct))\n",
    "            return res\n",
    "        \n",
    "        return f(n - 1, Counter(letters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        total = Counter(letters)\n",
    "        ws = []\n",
    "        for word in words:\n",
    "            tmp = 0\n",
    "            for ch in word:\n",
    "                tmp += score[ord(ch) - ord('a')]\n",
    "            ws.append(tmp)\n",
    "\n",
    "        def check(cnt, total):\n",
    "            for k in cnt.keys():\n",
    "                if cnt[k] > total[k]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        n = len(words)\n",
    "        ans = 0\n",
    "        for mask in range(1, 2 ** n):\n",
    "            curs = 0\n",
    "            flag = True\n",
    "            cnt = Counter()\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    curs += ws[i]\n",
    "                    cnt += Counter(words[i])\n",
    "                    if not check(cnt, total):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                print(bin(mask), cnt, total, ans, curs)\n",
    "                ans = max(ans, curs)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        words_len = len(words)\n",
    "        words_cout= [[0]*26 for i in range(words_len)]\n",
    "        # words_cout= []\n",
    "        for i in range(words_len):\n",
    "            for w in words[i]:\n",
    "                words_cout[i][ord(w)-97]+=1\n",
    "        a_count = [0]*26\n",
    "        for a in letters:\n",
    "            a_count[ord(a)-97]+=1\n",
    "        def check(index):\n",
    "            word = words[index]\n",
    "            for w in word:\n",
    "                w_ord = ord(w)-97\n",
    "                if a_count[w_ord] < words_cout[index][w_ord]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # def traceback(i):\n",
    "        #     if i>=words_len:\n",
    "        #         return 0\n",
    "        #     if not check(i):\n",
    "        #         return traceback(i+1)\n",
    "        #     t = 0 \n",
    "        #     soc = 0\n",
    "        #     for w in words[i]:\n",
    "        #         w_ord = ord(w)-97\n",
    "        #         a_count[w_ord]-=1\n",
    "        #         print(words[i], w_ord)\n",
    "        #         soc+= score[w_ord]\n",
    "        #     for j in range(i+1, words_len):\n",
    "        #         t_s = traceback(j)\n",
    "        #         soc += t_s\n",
    "        #         t = max(t, soc)\n",
    "        #         soc-= t_s\n",
    "        #     for w in words[i]:\n",
    "        #         a_count[w_ord]+=1\n",
    "        #     return max(t, soc)\n",
    "                    \n",
    "        def dfs(i):\n",
    "            if i <0:\n",
    "                return 0\n",
    "            t = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if check(j):\n",
    "                    not_selct= dfs(j-1)\n",
    "                    # print(\"not_selct\",not_selct)\n",
    "                    soc = 0\n",
    "                    for w in words[j]:\n",
    "                        w_ord = ord(w)-97\n",
    "                        a_count[w_ord]-=1\n",
    "                        # print(words[j], w_ord)\n",
    "                        soc+= score[w_ord]\n",
    "                    # print(\"soc\",soc)    \n",
    "                    select_ = soc+ dfs(j-1)\n",
    "\n",
    "                    # print(\"select_\",select_)\n",
    "                    t = max(t, not_selct,select_)\n",
    "                    for w in words[j]:\n",
    "                        w_ord = ord(w)-97\n",
    "                        a_count[w_ord]+=1\n",
    "            # print(t)\n",
    "            return t\n",
    "\n",
    "        # ans = 0\n",
    "        # for i in range(words_len):\n",
    "        #     ans = max(ans, dfs(i))\n",
    "        return dfs(words_len-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        score = dict(zip(ascii_lowercase, score))  # 字母对应的分数\n",
    "\n",
    "        def dfs(i: int, total: int) -> None:\n",
    "            if i < 0: \n",
    "                nonlocal ans\n",
    "                ans = max(ans, total)\n",
    "                return\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            # 选 words[i]\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if left[c] == 0: \n",
    "                    for c in words[i][:j]:  \n",
    "                        left[c] += 1\n",
    "                    return\n",
    "                left[c] -= 1  \n",
    "                total += score[c]\n",
    "            dfs(i - 1, total)\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "\n",
    "        dfs(len(words) - 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = Counter(letters)\n",
    "        score = dict(zip(ascii_lowercase, score))\n",
    "\n",
    "        def dfs(i, total):\n",
    "            if i < 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, total)\n",
    "                return \n",
    "            \n",
    "            # 不选words[i]\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            # 选words[i]\n",
    "            for j, c in enumerate(words[i]):\n",
    "                if left[c] > 0:\n",
    "                    left[c] -= 1\n",
    "                    total += score[c]\n",
    "                else:\n",
    "                    # 如果这个单词加到一半加不下去了，没有letter可选了，进行回溯，把加过去的去掉\n",
    "                    for c in words[i][:j]:\n",
    "                        left[c] += 1\n",
    "                    return\n",
    "            dfs(i - 1, total)\n",
    "\n",
    "            for c in words[i]:\n",
    "                left[c] += 1\n",
    "\n",
    "        dfs(len(words) - 1, 0)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        n = len(words)\n",
    "        @cache\n",
    "        def dfs(i, l):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            s = 0\n",
    "            l2 = l\n",
    "            for c in words[i]:\n",
    "                if c not in l2:\n",
    "                    return dfs(i+1, l)\n",
    "                s += score[ord(c)-ord('a')]\n",
    "                l2 = l2.replace(c, '', 1)\n",
    "\n",
    "            return max(dfs(i+1, l), s + dfs(i+1, l2))\n",
    "        return dfs(0, \"\".join(letters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ws = [Counter(i) for i in words]\n",
    "        letters = Counter(letters)\n",
    "        n = len(words)\n",
    "\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            \n",
    "            d = {}\n",
    "            \n",
    "            for i in range(n):\n",
    "                if state >> i & 1:\n",
    "                    for k, v in ws[i].items():\n",
    "                        d[k] = d.get(k, 0) + v\n",
    "                        if d[k] > letters[k]:\n",
    "                            return 0\n",
    "            ans = sum([score[ord(ch) - 97] * d[ch] for ch in d])\n",
    "            # 处理未选的情况\n",
    "            for i in range(n):\n",
    "                if state >> i & 1 == 0:\n",
    "                    ans = max(ans, dfs(state | 1 << i))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        ws = [Counter(i) for i in words]\n",
    "        letters = Counter(letters)\n",
    "        n = len(words)\n",
    "\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            d = {}\n",
    "            for i in range(n):\n",
    "                if state >> i & 1:\n",
    "                    for k, v in ws[i].items():\n",
    "                        d[k] = d.get(k, 0) + v\n",
    "                        if d[k] > letters[k]:\n",
    "                            return 0\n",
    "            ans = sum([score[ord(ch) - 97] * d[ch] for ch in d])\n",
    "            # 处理未选的情况\n",
    "            for i in range(n):\n",
    "                if state >> i & 1 == 0:\n",
    "                    ans = max(ans, dfs(state | 1 << i))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:\n",
    "        # 统计单词需要的字母-个数\n",
    "        words_cnt = [Counter(word) for word in words]\n",
    "        # 统计字符集的字母情况\n",
    "        letters_cnt = Counter(letters)\n",
    "        n = len(words)\n",
    "\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            # 统计当前状态下字符占用情况\n",
    "            d = dict()\n",
    "            for i in range(n):\n",
    "                # 当前状态已选第i个word\n",
    "                if state >> i & 1 == 1:\n",
    "                    for ch, v in words_cnt[i].items():\n",
    "                        d[ch] = d.get(ch, 0) + v\n",
    "                        # 字符集不支持，这个state不合理\n",
    "                        if d[ch] > letters_cnt.get(ch, 0):\n",
    "                            return 0\n",
    "            ans = sum([score[ord(ch)-ord('a')]* d[ch] for ch in d])\n",
    "            \n",
    "            for i in range(n):\n",
    "                if state >> i & 1 == 0:\n",
    "                    ans = max(ans, dfs(state | 1<<i))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n",
    "\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
